package jjn.carl.backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * @author Jiang Jining
 * @since 2023-07-23 22:43
 */
public class LeetCode17 {
    
    private static final Map<Character, List<String>> KEY_MAP = Map.of('2', List.of("a", "b", "c"),
            '3', List.of("d", "e", "f"), '4', List.of("g", "h", "i"),
            '5', List.of("j", "k", "l"), '6', List.of("m", "n", "o"),
            '7', List.of("p", "q", "r", "s"), '8', List.of("t", "u", "v"),
            '9', List.of("w", "x", "y", "z"));
    
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) {
            return result;
        }
        backtrack(digits, new StringBuilder(), result, 0);
        return result;
    }
    
    private void backtrack(String digits, StringBuilder stringBuilder, List<String> result, int startIndex) {
        if (stringBuilder.length() > digits.length()) {
            return;
        }
        if (stringBuilder.length() == digits.length()) {
            result.add(stringBuilder.toString());
            return;
        }
        for (int i = startIndex; i < digits.length(); i++) {
            char c = digits.charAt(i);
            List<String> options = KEY_MAP.get(c);
            for (String option : options) {
                stringBuilder.append(option);
                backtrack(digits, stringBuilder, result, i + 1);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String digits = scanner.nextLine();
        List<String> result = new LeetCode17().letterCombinations(digits);
        System.out.println("result = " + result);
    }
}
